package  main.java.leetcode.editor.cn;
//2022-05-25 10:01:25
//把字符串 s 看作是 “abcdefghijklmnopqrstuvwxyz” 的无限环绕字符串，所以 s 看起来是这样的： 
//
// 
// "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...." . 
// 
//
// 现在给定另一个字符串 p 。返回 s 中 唯一 的 p 的 非空子串 的数量 。 
//
// 
//
// 示例 1: 
//
// 
//输入: p = "a"
//输出: 1
//解释: 字符串 s 中只有一个"a"子字符。
// 
//
// 示例 2: 
//
// 
//输入: p = "cac"
//输出: 2
//解释: 字符串 s 中的字符串“cac”只有两个子串“a”、“c”。.
// 
//
// 示例 3: 
//
// 
//输入: p = "zab"
//输出: 6
//解释: 在字符串 s 中有六个子串“z”、“a”、“b”、“za”、“ab”、“zab”。
// 
//
// 
//
// 提示: 
//
// 
// 1 <= p.length <= 10⁵ 
// p 由小写英文字母构成 
// 
// Related Topics 字符串 动态规划 👍 233 👎 0

import java.util.Arrays;

class UniqueSubstringsInWraparoundString {
    public static void main(String[] args) {
        //创建该题目的对象方便调用
        Solution solution = new UniqueSubstringsInWraparoundString().new Solution();
        solution.findSubstringInWraproundString("zab");
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int findSubstringInWraproundString(String p) {

        int n = p.length();
        int[] dp = new int[26];
        dp[p.charAt(0)-'a'] = 1;  //第一个元素
        int count = 1;

        for(int i = 1;i<n;i++){
            char pre = p.charAt(i-1);
            char cut = p.charAt(i);

            int res = (cut-pre)%26;

            if(res == 1 || res == -25){
                count++;
            }else {
                count = 1;
            }
            dp[cut-'a'] = Math.max(count,dp[cut-'a']);
        }
        int sum = 0;
        sum = Arrays.stream(dp).sum();
        return sum;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
